
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0849
 * @Author : WangRuoyu 
 * @Date : 2023/5/22 9:41
 */

#include "iostream"

using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int g[n + 1][n + 1];
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            g[i][j] = 0x3f3f3f3f;
        }
    }
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        if (a != b) {
            g[a][b] = min(g[a][b], c);
        }
    }

    int dis[n + 1];
    bool st[n + 1];
    for (int i = 0; i <= n; ++i) {
        dis[i] = 0x3f3f3f3f;
        st[i] = false;
    }

    dis[1] = 0;

    for (int i = 0; i < n; ++i) {
        int j = -1;
        for (int k = 1; k <= n; ++k) {
            if (!st[k] && (j == -1 || dis[j] > dis[k])) {
                j = k;
            }
        }
        if (dis[j] > 1e6) break;
        st[j] = true;
        for (int k = 1; k <= n; ++k) {
            dis[k] = min(dis[k], dis[j] + g[j][k]);
        }
    }

    if (dis[n] > 1e6) {
        printf("-1");
    } else {
        printf("%d ", dis[n]);
    }

    return 0;
}